package leetcode;

import java.util.*;

public class LC6 {
    public static void main(String[] args) {
        LC6 lc6 = new LC6();
        System.out.println(lc6.threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
        System.out.println(lc6.threeSum(new int[]{0,0,0}));
        System.out.println(lc6.threeSum(new int[]{0,0,0,0}));
        System.out.println(lc6.threeSum(new int[]{-2,-2,-2,-1,2,4}));
        System.out.println(lc6.threeSum(new int[]{-2,-2,-1,-1,2,3}));
        System.out.println(lc6.threeSum(new int[]{-1,0,1,2,-1,-4,-2,-3,3,0,4}));
    }
    //2024-11-12 回顾 3指针解法
    // 将题目分解为两数之和为另一个数
    public List<List<Integer>> threeSum(int[] nums){
        List<List<Integer>> ans = new ArrayList<>();
        if (nums.length < 3) return ans;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i-1]) continue;
            int l = i+1, r = nums.length-1;
            while(l < r){
                if(nums[i] + nums[l] + nums[r] < 0) {
                    l++;
                    continue;
                }
                if(nums[i] + nums[l] + nums[r] == 0){
                    List<Integer> an = new ArrayList<>();
                    an.add(nums[i]);
                    an.add(nums[l]);
                    an.add(nums[r]);
                    ans.add(an);
                }
                r--;
                while(nums[r] == nums[r + 1] && r > l)
                    r--;
            }
        }
        return ans;
    }
    public List<List<Integer>> threeSum1(int[] nums) {
//        Arrays.sort(nums);
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        Set<List<Integer>> lll = new HashSet<>();
        for(int i = 0 ; i < nums.length; i++){
            for (int j = i+1; j < nums.length; j++) {
                Integer k = map.get(-nums[i] - nums[j]);
                if (k != null && k != i && k != j){
                    List<Integer> ll = new ArrayList<>();
                    ll.add(nums[i]);
                    ll.add(nums[j]);
                    ll.add(nums[map.get(-nums[i]-nums[j])]);
                    ll.sort(Integer::compareTo);
                    lll.add(ll);
                }
            }
        }
        return lll.stream().toList();
    }
}
